//
//  Array.swift
//  JNLeetCode
//
//  Created by Renju Jiang on 2018/12/21.
//  Copyright © 2018 jiangrenju. All rights reserved.
//

import Foundation

class LeetCodeArray {
    
    func threeSumByLC(_ nums: [Int]) -> [[Int]] {
        var ret = [[Int]]()
        if nums.count <= 2 {
            return ret
        }
        
        let nums = nums.sorted{ $0 < $1 }
        for i in 0 ..< nums.count {
            //let say nums[i] is the first element, the result requires unique triplets
            //which means if there are a few elements are the same value, we can start calculate sum from the last one
            //so we can terminate this time iteration and start from i+1, until we find the last continuous same i
            if i > 0 && nums[i] == nums[i-1] {
                continue
            }
            
            let target = -nums[i]
            var front = i + 1
            var end = nums.count - 1
            
            while(front < end){
                let sum = nums[front] + nums[end]
                if sum > target{
                    end -= 1
                }else if sum < target{
                    front += 1
                }else{
                    let result = [nums[i], nums[front], nums[end]]
                    ret.append(result)
                    
                    //do the same thing here move forward and ignore all the front with same value
                    while(front < end && nums[front] == result[1]){
                        front += 1
                    }
                    
                    //ignore all the end with same value until we get a new end value
                    while(front < end && nums[end] == result[2]){
                        end -= 1
                    }
                }
            }
        }
        
        return ret
    }

    func threeSum(_ nums: [Int]) -> [[Int]] {
        if nums.count < 3 {
            return []
        }
        
        var sortNums = nums
        quickSort(nums: &sortNums, start: 0, end: sortNums.count-1)
        let target = 0
        var result: [[Int]] = []
        
        for i in 0..<sortNums.count {
            if i > 0 && sortNums[i] == sortNums[i-1] {
                continue
            }
            if sortNums[i] > target {
                break
            }
            
            let twoSum = target - sortNums[i]
            var left = i + 1
            var right = sortNums.count - 1
            
            while left < right {
                
                let sum = sortNums[left] + sortNums[right]
                
                if sum > twoSum {
                    
                    right -= 1
                    
                } else if sum < twoSum {
                    
                    left += 1
                    
                } else {
                    let arr = [sortNums[i], sortNums[left], sortNums[right]]
                    result.append(arr)
                    left += 1
                    right -= 1

                    while left < right && sortNums[left] == sortNums[left-1] {
                        left += 1
                    }
                    
                    while left < right && sortNums[right] == sortNums[right+1] {
                        right -= 1
                    }
                }
                
            }
        }
        
        return result
    }
    
    func quickSort(nums: inout [Int], start: Int, end: Int) {
        
        if start >= end {
            return
        }
        
        var left = start
        var right = end
        
        let reference = nums[left]
        
        while left < right {
            
            while left < right && nums[right] >= reference {
                right -= 1
            }
            
            while left < right && nums[left] <= reference {
                left += 1
            }
            
            if left < right {
                let tmp = nums[right]
                nums[right] = nums[left]
                nums[left] = tmp
            }
        }
        
        nums[start] = nums[left]
        nums[left] = reference
        
        quickSort(nums: &nums, start: start, end: left - 1)
        quickSort(nums: &nums, start: left + 1, end: end)
    }

    func twoSumFuncByHashMap(_ nums: [Int], start: Int, end: Int, target: Int) -> [[Int]] {
        guard start < nums.count && end < nums.count else { return [] }
        
        var result: [[Int]] = []
        var map: [Int: Int] = [:]
        
        for i in start...end {
            let m = nums[i]
            if map.keys.contains(target-m) {
                let arr = [m, target-m]
                if !result.contains(arr) {
                    result.append(arr)
                }
            }
            map[m] = 1
        }
        return result
    }
    
    
}


